template<typename T>
void Foo<T>::f() {}

template <typename T>
ListNode<T>* ListNode<T>::insertAsSucc(T const& e)
{
  ListNodePosi(T) node = new ListNode(e, this, succ);
  succ->pred = node; succ = node;
  return node;
}

template <typename T>
ListNode<T>* ListNode<T>::insertAsPred(T const& e)
{
  ListNodePosi(T) node = new ListNode(e, pred, this);
  pred->succ = node;
  pred = node;
  return node;
}

template <typename T>
List<T>::List()
{
  init();
}

template <typename T>
List<T>::List(List<T> const& p)
{
  copyNodes(p.first(), p._size);
}

template <typename T>
List<T>::List(List<T> const& L, int r, int n)
{
  copyNodes(L[r], n);
}

template <typename T>
List<T>::List(ListNodePosi(T) p, int n)
{
  copyNodes(p, n);
}

template <typename T>
void List<T>::append(T const& e)
{
  insertAsLast(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertA(ListNodePosi(T) p, T const& e)
{
  _size++;
  p->insertAsSucc(e);
  return p->succ;
}

template <typename T>
ListNodePosi(T) List<T>::insertB(ListNodePosi(T) p, T const& e)
{
  _size++;
  p->insertAsPred(e);
  return p->pred;
}

template <typename T>
void List<T>::copyNodes(ListNodePosi(T) p, int n)
{
  init();
  while (n--) {
    insertAsLast(p->data);
    p = p->succ;
  }
}

template <typename T>
void List<T>::init()
{
  _size = 0;
  header = new ListNode<T>();
  tailer = new ListNode<T>();
  header->succ = tailer; header->pred = nullptr;
  tailer->pred = header; tailer->succ = nullptr;
}

template <typename T>
T& List<T>::operator[](int r) const
{
  auto node = first();
  while (0 < r--) node = node->succ();
  return node->data;
}

template <typename T>
ListNodePosi(T) List<T>::insertAsFirst(T const& e)
{
  _size++;
  return header->insertAsSucc(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertAsLast(T const& e)
{
  _size++;
  return tailer->insertAsPred(e);
}

template <typename T>
T List<T>::remove(ListNodePosi(T) p)
{
  T e = p->data;
  p->pred->succ = p->succ;
  p->succ->pred = p->pred;
  delete p, _size--;
  return e;
}

template <typename T>
List<T>::~List()
{
  clear(); delete header; delete tailer;
}

template <typename T>
int List<T>::clear()
{
  int _old = _size;
  while (0 < _size--) remove(header->succ);
  return _old;
}

template <typename T>
int List<T>::deduplicate()
{
  if (_size < 2) return 0;
  int oldSize = _size;
  ListNodePosi(T) node = header;
  Rank r = 0;
  while ((node = node->succ) != tailer)
  {
    auto q = find(node->data, r, node);
    q ? remove(q) : r++;
  }
  return oldSize - _size;
}

template <typename T>
ListNodePosi(T) List<T>::find(T const& e) const
{
  return find(e, _size, tailer);
}

template <typename T>
ListNodePosi(T) List<T>::find(T const& e, int n, ListNodePosi(T) p) const
{
  while (0 < n--)
    if (e == (p = p->pred)->data) return p;

  return nullptr;
}

template <typename T>
void List<T>::traverse(void (*visit)(T&))
{
  for (ListNodePosi(T) p = header->succ; p != tailer; p = p->succ)
    visit(p->data);
}

template <typename T>
template <typename VST>
void List<T>::traverse(VST&)
{
  for (ListNodePosi(T) p = header->succ; p != tailer; p = p->succ)
    visit(p->data);
}

/// <summary>
/// list must be ordered.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <returns></returns>
template <typename T>
int List<T>::uniquify()
{
  if (_size < 2) return 0;
  int oldSize = _size;
  auto p = first();
  ListNodePosi(T) q;
  while ((q = p->succ) != tailer)
  {
    if (p->data != q->data) p = q;
    else remove(q);
  }
  return oldSize - _size;
}

template <typename T>
ListNode<T>* List<T>::search(T const& e) const
{
  search(e, _size, tailer);
}

/// <summary>
/// search in ordered list
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="e"></param>
/// <param name="n"></param>
/// <param name="p"></param>
/// <returns></returns>
template <typename T>
ListNode<T>* List<T>::search(T const& e, int n, ListNode<T>* p) const
{
  while (n-- >= 0)
    if ((p = p->succ)->data <= e) break;
  return p;
}

template <typename T>
void List<T>::insertSort(ListNodePosi(T) p, int n)
{
  for (int r = 0; r < n; r++)
  {
    insertA(search(p->data, r, p), p->data);
    p = p->succ; remove(p->pred);
  }
}

template <typename T>
void List<T>::selectionSort(ListNodePosi(T) p, int n)
{
  ListNodePosi(T) head = p->pred; ListNodePosi(T) tail = p;
  for (int i = 0; i < n; i++) tail = tail->succ;
  while (1 < n)
  {
    ListNodePosi(T) max = selectMax(head->succ, n);
    insertB(tail, remove(max));
    tail = tail->pred; n--;
  }
}

template <typename T>
int List<T>::disordered() const
{
  int n = _size;
  for (ListNodePosi(T) curr = first(); 0 < n; n--)
  {
    if (!std::less<T>{ }(curr->data, (curr = curr->succ)->data))
      return false;
  }

  return true;
}

template <typename T>
void List<T>::sort(ListNodePosi(T) p, int n)
{
  switch (rand() % 3)
  {
  case 1:
    selectionSort(p, n); break;
  case 2:
    mergeSort(p, n); break;
  default:
    insertSort(p, n); break;
  }
}

/// <summary>
/// Ordered list
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="ListNodePosi"></param>
/// <param name=""></param>
/// <param name=""></param>
/// <param name=""></param>
/// <param name=""></param>
template <typename T>
void List<T>::merge(List<T>& L)
{
  merge(first(), size, L, L.first(), L._size);
}

/// <summary>
/// Ordered list
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="ListNodePosi"></param>
/// <param name=""></param>
/// <param name=""></param>
/// <param name=""></param>
/// <param name=""></param>
template <typename T>
void List<T>::merge(ListNodePosi(T)& p, int n, List<T>& L, ListNodePosi(T) q, int m)
{
  ListNodePosi(T) pp = p->pred;
  while (0 < m)
  {
    if ((0 < n) && (p->data <= q->data))
    {
      if (q == (p = p->succ)) break;
      n--;
    }
    else
    {
      insertB(p, L.remove((q = q->succ)->pred));
      m--;
    }
  }
  p = pp->succ;
}

template <typename T>
void List<T>::mergeSort(ListNodePosi(T)& p, int n)
{
  if (n < 2) return;
  int m = n >> 1;
  ListNodePosi(T) q = p;
  for (int i = 0; i < m; i++)
    q = q->succ;
  mergeSort(p, m);
  mergeSort(q, n - m);
  merge(p, m, *this, q, n - m);
}

template <typename T>
ListNode<T>* List<T>::selectMax()
{
  return selectMax(header->succ, _size);
}

template <typename T>
ListNode<T>* List<T>::selectMax(ListNode<T>* p, int n) const
{
  ListNodePosi(T) _max = p;
  for (ListNodePosi(T) curr = p; 1 < n; n--)
  {
    if (!std::less<T>{ }((curr = curr->succ)->data, _max->data))
      _max = curr;
  }

  return _max;
}